package class01

// 给定一个数组arr, 从左到右依次表示x轴上从左往右点的位置
// 给定一个正整数K，返回如果有一根长度为K的绳子，最多能盖住几个点
// 绳子的边缘点碰到x轴上的点，也算盖住。

func CordCoverMaxPoint1(arr []int, k int) int {
	var ans int
	var left int
	for right := 0; right < len(arr); right++ {
		left = getMostLeftIndex(arr, right, arr[right]-k)
		ans = max(ans, right-left+1)
	}
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func getMostLeftIndex(arr []int, right int, num int) int {
	var left int
	var mid int
	var index int
	for left <= right {
		mid = left + (right-left)>>1
		if arr[mid] >= num {
			index = mid
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return index
}

func CordCoverMaxPoint2(arr []int, k int) int {
	var left int
	var right int
	var ans int
	n := len(arr)
	for left < n {
		for right < n && arr[right] - arr[left] <= k {
			right++
		}
		ans = max(ans, right-left)
		left++
	}
	return ans
}
